/* 

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

*/

/**
 * @param {number[][]} grid
 * @return {number}
 */
// dp
var minPathSum = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = Array.from(new Array(m), _ => new Array(n).fill(Infinity));

    dp[0][0] = grid[0][0];

    for (let col = 1; col < n; col++) {
        dp[0][col] = dp[0][col - 1] + grid[0][col];
    }
    for (let row = 1; row < m; row++) {
        dp[row][0] = dp[row - 1][0] + grid[row][0];
    }

    for (let row = 1; row < m; row++) {
        for (let col = 1; col < n; col++) {
            dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col];
        }
    }

    return dp[m - 1][n - 1];
};